#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 2106. 摘水果
// https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/description/

class Solution
{
public:
    int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k)
    {

        auto itLeft = lower_bound(fruits.begin(), fruits.end(), startPos - k, [](const vector<int> &num, int target)
                                  { return num[0] < target; });

        int ans = 0;

        int left = itLeft - fruits.begin();
        int right = left;
        int curSum = 0;
        int n = fruits.size();
        for (right; right < n && fruits[right][0] <= startPos; right++)
        {
            curSum += fruits[right][1];
        }
        ans = curSum;
        // 滑动窗口
        for (right; right < n && fruits[right][0] <= startPos+ k; right++){
            curSum += fruits[right][1];
            while(fruits[right][0]* 2 - startPos - fruits[left][0] > k && fruits[right][0] + startPos - fruits[left][0]*2 > k){
                curSum -= fruits[left][1];
                left++;
            }
            ans = max(ans, curSum);
        }
        return ans;
    }
};

int main()
{
    return 0;
}